package com.cong._64;

class Solution {
    public int minPathSum(int[][] grid) {
        int i = grid.length;
        int j = grid[0].length;
        int[][] pathMap = new int[i + 1][j + 1];

        for(int row = i; row > 0;row--) {
            for (int col = j;col > 0;col--) {
                if (col == j && row == i) {
                    pathMap[row][col] = grid[row - 1][col - 1];
                    continue;
                }
                int thisLen = grid[row - 1][col - 1];
                int leastPathLen = -1 >>> 1;
                if (col < j) {
                    leastPathLen = Math.min(leastPathLen, thisLen + pathMap[row][col + 1]);
                }
                if (row < i) {
                    leastPathLen = Math.min(leastPathLen, thisLen + pathMap[row + 1][col]);
                }
                pathMap[row][col] = leastPathLen;
            }
        }
        return pathMap[1][1];
    }

    public static void main(String[] args) {
        int[][] grid = new int[][] {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        int[][] grid_2 = new int[][] {
                {1, 2, 3},
                {4, 5, 6}
        };
        int res = new Solution().minPathSum(grid);
        System.out.println(res);
        System.out.println(new Solution().minPathSum(grid_2));
    }
}
